package org.chnxi.study.datastructrues.recursion;

/**
 * 使用递归的方式查找迷宫线路
 * 未加入最短路径
 */
public class MiGong {

    public static void main(String[] args) {

        //创建地图
        int[][] map = createMap();

        //输出地图样子
        printMiGong(map);

        // 说明：
        // 1.出发位置（1，1），
        // 结束位置（6，5），表示走到出口
        // 使用0表示没有走过，使用1表示墙，使用2表示可以走通，使用3表示走过单不通
        // 在走迷宫时，需要确定一个策略，如：查找优先级：下->右->上->左，如果走不通，再回溯
        setWay(map , 1, 1);
        System.out.println("小球走过的线路：");
        printMiGong(map);

        map = createMap();
        setWay2(map , 1, 1);
        System.out.println("小球走过的线路");
        printMiGong(map);
    }

    /**
     * 创建地图，使用二位数组进行模拟
     * @return
     */
    public static int[][] createMap(){
        //创建迷宫，使用二位数组
        int[][] map = new int[8][7];
        //先把上下全部置位1，表示墙
        for (int i=0;i<7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }

        //把左右两侧全部置位1，表示墙
        for (int i=0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }

        //设置挡板
        map[3][1]=1;
        map[3][2]=1;

        return map;
    }

    /**
     * 使用递归查找线路
     * @param map 表示地图
     * @param i 从哪个位置开始找
     * @param j 从哪个位置开始找
     * @return 如果找到通路就返回true，如果没找到就返回false
     */
    public static boolean setWay(int[][] map , int i , int j){
        if(map[6][5] == 2){ //已经走到了出口
            return true;
        }else{
            if(map[i][j] == 0){ //当前节点还没有走过
                //下->右->上->左
                map[i][j] = 2; //假定该点可以走通
                if(setWay(map , i+1 , j)){ //向下走
                    return true;
                }else if(setWay(map , i , j+1)){ //向右走
                    return true;
                }else if(setWay(map , i - 1, j)){ //向上走
                    return true;
                }else if(setWay(map , i , j-1)){ //向左走
                    return true;
                }else{
                    //说明该点走不通，是死路
                    map[i][j] = 3;
                    return false;
                }
            }else{ //可能是1（墙），2（走过），3（死路）
                return false;
            }
        }
    }

    /**
     * 修改找路的策略，改成：上->右->下->左
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay2(int[][] map , int i , int j){
        if(map[6][5] == 2){ //已经走到了出口
            return true;
        }else{
            if(map[i][j] == 0){ //当前节点还没有走过
                //下->右->上->左
                map[i][j] = 2; //假定该点可以走通
                if(setWay2(map , i-1 , j)){ //向下走
                    return true;
                }else if(setWay2(map , i , j+1)){ //向右走
                    return true;
                }else if(setWay2(map , i+1, j)){ //向上走
                    return true;
                }else if(setWay2(map , i , j-1)){ //向左走
                    return true;
                }else{
                    //说明该点走不通，是死路
                    map[i][j] = 3;
                    return false;
                }
            }else{ //可能是1（墙），2（走过），3（死路）
                return false;
            }
        }
    }

    /**
     * 在控制台输出地图
     * @param map
     */
    static void printMiGong(int[][] map){
        for (int i=0;i<8;i++){
            for (int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println("");
        }
    }

}
